package leetcode_cn;

import java.util.Arrays;

/**
 * 最接近的三数之和
 *
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-09-06 14:22
 */
public class ThreeSumClosest {

    public int solution(int[] nums,int target){
        if (nums == null || nums.length == 0) return 0;
        int len = nums.length,min = Integer.MAX_VALUE;
        int res = 0;
        Arrays.sort(nums);
        for (int i = 0; i < len-2; i++) {
            //1， 固定一个数 nums[i]
            int left = i + 1,right = len-1;

            while (left < right){
                int temp = nums[left] + nums[right] + nums[i] - target;
                if (Math.abs(temp) < min){
                    min = Math.abs(temp);
                    res = nums[left] + nums[right] + nums[i];
                }
                if (temp == 0){
                    return target;
                }else if (temp > 0){
                    while (left < right && nums[right-1] == nums[right]) right--;
                    right--;
                }else {
                    while (left < right && nums[left+1] == nums[left]) left++;
                    left++;
                }
            }

        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new ThreeSumClosest().solution(new int[]{-1, 2, 1, -4}, 1));
        System.out.println(new ThreeSumClosest().solution(new int[]{0,2,1,-3}, 1));
    }
}
